/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-12-25
 * Time: 22:23
 */
import java.util.HashSet;
import java.util.Scanner;

public class Main18 {
    //图着色思路：
    /*
    不过和之前做过的题的不同是，这次他会给颜色的种类m,所以说是存在可能无法完成着色的情况的
    回溯算法
    从下标为0的点开始走，知道所有的点完成着色，相邻的点之间不能使用同一种颜色
     */

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        // n个点，m个边
        int[][] array=new int[n][n];
        for(int p=0;p<m;p++){
            int i=sc.nextInt()-1;
            int j=sc.nextInt()-1;
            array[i][j]=1;
            array[j][i]=1;
        }

        int[] arr=new int[n];
        int color=func(array,n,arr);

//        for(int i=0;i<n;i++){
//            System.out.print(arr[i]+"  ");
//        }
//
//        System.out.println();

        System.out.println(color);
    }

    public static int func(int[][] array,int n,int[] arr){
        /*
        array数组存放点之间的连接关系
        n有几个点
        m有几种颜色
        arr存放每个点最终所涂颜色（值为0表示没有涂色）
         */
        int color=0;

        arr[0]=1;//第一个点肯定是第一个颜色了（颜色范围：【1，m】）
        color++;
        int m=1;

        int num=1;//记录有几个点已经完成着色

        int q=0;

        while(num<n){
            int p=num;
            for(int i=1;i<n;i++){
                if(arr[i]==0){
                    //没有涂色
                    //看看和它相连的点都涂了什么颜色，涂它们没涂过的颜色， 要是所有的颜色都被涂过了，那么就说明是找不到的就直接返回
                    int[] ret=new int[m+1];
                    int s=0;//此次查询中有几个颜色已经被使用了

                    //找到值最小的（和它相连的点）没涂过的颜色即可
                    for(int j=0;j<n;j++){
                        if(array[i][j]!=0){
                            //相连
                            ret[arr[j]]=1;
                        }
                    }

                    //找到还没有被使用过的颜色
                    for(int j=1;j<=m;j++){
                        if(ret[j]==0){
                            arr[i]=j;
                            q=i;
                        }else{
                            s++;
                        }
                    }

                    if(s==m){
                        //s==m，就代表所有的颜色都已经被使用过了，无解
                        //System.out.println("没找到，不存在");
                        //return 0;
                        m++;
                        arr[i]=m;
                    }

                    if(arr[i]==0){

                    }else{
                        num++;
                    }
                }
            }

            if(num==p && num>0){
                //此次寻找没有点被涂色，证明树的本层是不合适的，所以需要回溯到它的上一层去
                arr[q]=0;
                num--;
            }
        }

        //遍历arr数组， 看看它使用了几种颜色
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<n;i++){
            set.add(arr[i]);
        }
        color=set.size();

        return color;
    }

}

